import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

public class Test {
    //递归
    //一个方法在执行过程中调用自身，就称为“递归”
    //把原问题分解为小问题，小问题的解决方式和大问题解决方式是一样的
    //满足两个条件：1.自己调用自己 2.有一个终止条件（起始条件）
    //最难的地方就是如何能够确定 递推公式
    //递归浪费的空间比较多
    //数组的定义和使用
    //

    //汉诺塔
    public static void hanota(int n,char pose1,char pose2,char pose3){
        if(n == 1){
            move(pose1,pose3);
            return;
        }
        hanota(n-1,pose1,pose3,pose2);
        move(pose1,pose3);
        hanota(n-1,pose2,pose1,pose3);
    }
    public static void move(char pos1,char pose2){

        System.out.print(pos1 + "->" + pose2+" ");
    }

    public static void main(String[] args) {
        hanota(1,'A','B','C');
        System.out.println();
        hanota(2,'A','B','C');
        System.out.println();
        hanota(3,'A','B','C');
    }

    //斐波那契
    //不适用与递归 占用空间太大
    public static int fibnocio(int n) {
        if(n == 1 || n == 2){
            return 1;
        }
        return fibnocio(n - 1) + fibnocio(n - 2);
    }

    public static void main6(String[] args) {

        System.out.println(fibnocio(3));
    }

    //求每一位数字的和（例如1729 求1+7+2+9）
    public static int func5(int n){
        if(n <= 9) {
            return n;
        }
        return n %10 + func5(n / 10);
    }

    public static void main5(String[] args) {
        System.out.println(func5(1729));
    }

    //求1+2+3+4......+10
    public static int sum1(int n){
        if(n == 1){
            return 1;
        }
        return n+sum(n-1);
    }

    public static void main4(String[] args) {

        System.out.println(sum(10));
    }

    //按顺序打印一个数字的每一位（例如1234打印出1 2 3 4）
    public static void func4(int n ) {
        if (n <= 9) {
            System.out.println(n % 10);
            return;
        }
        func4(n / 10);
        System.out.println(n % 10);
    }

    public static void main3(String[] args) {

        func4(1234);
    }

/////////////////////////////////////
    public static int sum(int n){
        if (n == 1){
            return 1;
        }
        return n + sum(n - 1);
    }

    public static void main2(String[] args) {

        System.out.println(sum(10));
    }
///////////////////////////////////////////
    public static int fac(int n) {
        if(n == 1){
            return 1;
        }
        int tmp = n * fac(n -1);
        return tmp;
    }
    public static void main1(String[] args) {

        System.out.println(fac(5));
    }
}
